SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Partition problem</title>

</head>

Partition problem

</h1>

</header>

In <a href="Number_theory" title="Number theory">number theory</a> and <a href="Computer_science" title="Computer science">computer science</a>, the partition problem, or number partitioning,<a href="#cite_note-FOOTNOTEKorf1998-1">[1]</a> is the task of deciding whether a given <a href="Multiset" title="Multiset">multiset</a> S of positive integers can be <a href="Partition_of_a_set" title="Partition of a set">partitioned</a> into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>, there is a <a href="Pseudo-polynomial_time" title="Pseudo-polynomial time">pseudo-polynomial time</a> <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> solution, and there are <a href="Heuristic" title="Heuristic">heuristics</a> that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".<a href="#cite_note-hayes-2">[2]</a><a href="#cite_note-FOOTNOTEMertens2006[httpsbooksgooglecombooksid4YD6AxV95zECpgPA125_125]-3">[3]</a>

There is an <a href="Optimization_problem" title="Optimization problem">optimization version</a> of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, but can be solved efficiently in practice.<a href="#cite_note-multi-4">[4]</a>

The partition problem is a special case of two related problems:

<ul><li>In the <a href="Subset_sum_problem" title="Subset sum problem">subset sum problem</a>, the goal is to find a subset of S whose sum is a certain target number T given as input (the partition problem is the special case in which T is half the sum of S).</li>

<li>In <a href="Multiway_number_partitioning" title="Multiway number partitioning">multiway number partitioning</a>, there is an <a href="Integer" title="Integer">integer</a> parameter k, and the goal is to decide whether S can be partitioned into k subsets of equal sum (the partition problem is the special case in which k = 2).</li></ul>

However, it is quite different to the <a href="3-partition_problem" title="3-partition problem">3-partition problem</a>: in that problem, the number of subsets is not fixed in advance – it should be |S|/3, where each subset must have exactly 3 elements. 3-partition is much harder than partition – it has no pseudo-polynomial time algorithm unless <a href="P_%3D_NP" class="mw-redirect" title="P = NP">P = NP</a>.<a href="#cite_note-Garey_&_Johnson-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}. Both sets sum to 5, and they <a href="Partition_of_a_set" title="Partition of a set">partition</a> S. This solution is not unique. S1 = {3,1,1} and S2 = {2,2,1} is another solution.

Not every <a href="Multiset" title="Multiset">multiset</a> of positive integers has a partition into two subsets with equal sum. An example of such a set is S = {2,5}.

<div class="mw-heading mw-heading2"><h2 id="Computational_hardness">Computational hardness</h2></div>

The partition problem is NP hard. This can be proved by reduction from the <a href="Subset_sum_problem" title="Subset sum problem">subset sum problem</a>.<a href="#cite_note-6">[6]</a> An instance of SubsetSum consists of a set S of positive integers and a target sum T; the goal is to decide if there is a subset of S with sum exactly T.

Given such an instance, construct an instance of Partition in which the input set contains the original set plus two elements: z1 and z2, with z1 = sum(S) and z2 = 2T. The sum of this input set is sum(S) + z1 + z2 = 2 sum(S) + 2T, so the target sum for Partition is sum(S) + T.

<ul><li>Suppose there exists a solution S′ to the SubsetSum instance. Then sum(S′) = T, so sum(S′ ∪ z_1) = sum(S) + T, so S′ ∪ z_1 is a solution to the Partition instance.</li>

<li>Conversely, suppose there exists a solution S′′ to the Partition instance. Then, S′′ must contain either z1 or z2, but not both, since their sum is more than sum(S) + T. If S'' contains z1, then it must contain elements from S with a sum of exactly T, so S'' minus z1 is a solution to the SubsetSum instance. If S'' contains z2, then it must contain elements from S with a sum of exactly sum(S) − T, so the other objects in S are a solution to the SubsetSum instance.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Approximation_algorithms">Approximation algorithms</h2></div>

As mentioned above, the partition problem is a special case of multiway-partitioning and of subset-sum. Therefore, it can be solved by algorithms developed for each of these problems. Algorithms developed for <a href="Multiway_number_partitioning" title="Multiway number partitioning">multiway number partitioning</a> include:

<ul><li><a href="Greedy_number_partitioning" title="Greedy number partitioning">Greedy number partitioning</a> – loops over the numbers, and puts each number in the set whose current sum is smallest. If the numbers are not sorted, then the runtime is O(n) and the approximation ratio is at most 3/2 ("approximation ratio" means the larger sum in the algorithm output, divided by the larger sum in an optimal partition). Sorting the numbers increases the runtime to O(n log n) and improves the approximation ratio to 7/6. If the numbers are distributed uniformly in [0,1], then the approximation ratio is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}">

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}</annotation>

</semantics>

</math><img src="./a457a7db394b935809e7069f27e15ce88926781b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.738ex; height:4.843ex;" alt="{\textstyle 1+O\left({\frac {\log \log n}{n}}\right)}" loading="lazy"> <a href="Almost_surely" title="Almost surely">almost surely</a>, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 1+O\left({\frac {1}{n}}\right)}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 1+O\left({\frac {1}{n}}\right)}</annotation>

</semantics>

</math><img src="./ff660a8d18f48e07359894d5621fcd364e9cbc67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.115ex; height:3.343ex;" alt="{\textstyle 1+O\left({\frac {1}{n}}\right)}" loading="lazy"> in expectation.</li>

<li><a href="Largest_differencing_method" title="Largest differencing method">Largest Differencing Method</a> (also called the Karmarkar–Karp algorithm) sorts the numbers in descending order and repeatedly replaces numbers by their differences. The runtime complexity is O(n log n). In the worst case, its approximation ratio is similar – at most 7/6. However, in the average case it performs much better than the <a href="Greedy_algorithm" title="Greedy algorithm">greedy algorithm</a>: when numbers are distributed uniformly in [0,1], its approximation ratio is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 1+1/n^{\Theta (\log n)}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 1+1/n^{\Theta (\log n)}}</annotation>

</semantics>

</math><img src="./bfe2fbc6476e750c940f09e5c0dce152bd34119d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.987ex; height:3.176ex;" alt="{\textstyle 1+1/n^{\Theta (\log n)}}" loading="lazy"> in expectation. It also performs better in simulation experiments.</li>

<li>The <a href="Multifit_algorithm" title="Multifit algorithm">multifit algorithm</a> uses binary search combined with an algorithm for <a href="Bin_packing_problem" title="Bin packing problem">bin packing</a>. In the worst case, its approximation ratio is 8/7.</li>

<li>The <a href="Subset_sum_problem" title="Subset sum problem">subset sum problem</a> has an <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">FPTAS</a> which can be used for the partition problem as well, by setting the target sum to sum(S)/2.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Exact_algorithms">Exact algorithms</h2></div>

There are <a href="Exact_algorithm" title="Exact algorithm">exact algorithms</a>, that always find the optimal partition. Since the problem is NP-hard, such algorithms might take exponential time in general, but may be practically usable in certain cases. Algorithms developed for <a href="Multiway_number_partitioning" title="Multiway number partitioning">multiway number partitioning</a> include:

<ul><li>The <a href="Pseudopolynomial_time_number_partitioning" title="Pseudopolynomial time number partitioning">pseudopolynomial time number partitioning</a> takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(nm)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(nm)}</annotation>

</semantics>

</math><img src="./b9eee64c65f5cf5edf49bb5a1da6242b3d15544b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\textstyle O(nm)}" loading="lazy"> memory, where m is the largest number in the input.</li>

<li>The Complete Greedy Algorithm (CGA) considers all partitions by constructing a <a href="Binary_tree" title="Binary tree">binary tree</a>. Each level in the tree corresponds to an input number, where the root corresponds to the largest number, the level below to the next-largest number, etc. Each branch corresponds to a different set in which the current number can be put. Traversing the tree in <a href="Depth-first_search" title="Depth-first search">depth-first</a> order requires only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(n)}</annotation>

</semantics>

</math><img src="./e73234cd485b947e68d1d78823313db65ef226d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\textstyle O(n)}" loading="lazy"> space, but might take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(2^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(2^{n})}</annotation>

</semantics>

</math><img src="./87e7d38348af8ca63a6e198e78929f72639bb8f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.964ex; height:2.843ex;" alt="{\textstyle O(2^{n})}" loading="lazy"> time. The runtime can be improved by using a greedy heuristic: in each level, develop first the branch in which the current number is put in the set with the smallest sum. This algorithm finds first the solution found by <a href="Greedy_number_partitioning" title="Greedy number partitioning">greedy number partitioning</a>, but then proceeds to look for better solutions. Some variations of this idea are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well.<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a></li>

<li>The Complete Karmarkar–Karp algorithm (CKK) considers all partitions by constructing a binary tree. Each level corresponds to a pair of numbers. The left branch corresponds to putting them in different subsets (i.e., replacing them by their difference), and the right branch corresponds to putting them in the same subset (i.e., replacing them by their sum). This algorithm finds first the solution found by the <a href="Largest_differencing_method" title="Largest differencing method">largest differencing method</a>, but then proceeds to find better solutions. It runs substantially faster than CGA on random instances. Its advantage is much larger when an equal partition exists, and can be of several orders of magnitude. In practice, problems of arbitrary size can be solved by CKK if the numbers have at most 12 <a href="Significant_figures" title="Significant figures">significant digits</a>.<a href="#cite_note-9">[9]</a> CKK can also run as an <a href="Anytime_algorithm" title="Anytime algorithm">anytime algorithm</a>: it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances).<a href="#cite_note-FOOTNOTEKorf1998-1">[1]</a> It requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="O(n)">

<mrow>

</mrow>

</semantics>

</math><img src="./b5f77cd3ea7922fdedfe0394ede2434e3842f580.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="O(n)" loading="lazy"> space, but in the worst case might take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="O(2^{n})">

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</semantics>

</math><img src="./d5ef805487ed8047f438f0d766abb1fb4aec2162.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.964ex; height:2.843ex;" alt="O(2^{n})" loading="lazy"> time.</li></ul>

Algorithms developed for <a href="Subset_sum_problem" title="Subset sum problem">subset sum</a> include:

<ul><li>Horowitz and Sanhi – runs in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="O(2^{n/2}\cdot (n/2))">

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</semantics>

</math><img src="./3e9cc45eee92714e931d07e766c98b249706b072.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.816ex; height:3.343ex;" alt="O(2^{n/2}\cdot (n/2))" loading="lazy">, but requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="O(2^{n/2})">

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</semantics>

</math><img src="./e81051c5c14d60db1e7227c6fa44a7205718a1c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.607ex; height:3.343ex;" alt="O(2^{n/2})" loading="lazy"> space.</li>

<li>Schroeppel and Shamir – runs in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="O(2^{n/2}\cdot (n/4))">

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</semantics>

</math><img src="./ed050e19248212a2154066f096f4aebf3308b8cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.816ex; height:3.343ex;" alt="O(2^{n/2}\cdot (n/4))" loading="lazy">, and requires much less space – <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(2^{n/4})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(2^{n/4})}</annotation>

</semantics>

</math><img src="./1f35c9fd85b8b95f82c1bce9c7f34eda95712fd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.607ex; height:3.176ex;" alt="{\textstyle O(2^{n/4})}" loading="lazy">.</li>

<li>Howgrave-Graham and Joux – runs in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(2^{n/3})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(2^{n/3})}</annotation>

</semantics>

</math><img src="./18770048605c58deca48cffc5dd04e2b3430d372.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.607ex; height:3.176ex;" alt="{\textstyle O(2^{n/3})}" loading="lazy">, but it is a <a href="Randomized_algorithm" title="Randomized algorithm">randomized algorithm</a> that only solves the decision problem (not the optimization problem).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Hard_instances_and_phase-transition">Hard instances and phase-transition</h2></div>

Sets with only one, or no partitions tend to be hardest (or most expensive) to solve compared to their input sizes. When the values are small compared to the size of the set, perfect partitions are more likely. The problem is known to undergo a "<a href="Phase_transition" title="Phase transition">phase transition</a>"; being likely for some sets and unlikely for others. If m is the number of bits needed to express any number in the set and n is the size of the set then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m/n<1}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m/n<1}</annotation>

</semantics>

</math><img src="./586f2b7edbc70edf186da5e2adbb45678147f526.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.858ex; height:2.843ex;" alt="{\displaystyle m/n<1}" loading="lazy"> tends to have many solutions and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m/n>1}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m/n>1}</annotation>

</semantics>

</math><img src="./713b2a6165d771e8242b7f647dcc9d137f8c5f87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.858ex; height:2.843ex;" alt="{\displaystyle m/n>1}" loading="lazy"> tends to have few or no solutions. As n and m get larger, the probability of a perfect partition goes to 1 or 0 respectively. This was originally argued based on empirical evidence by Gent and Walsh,<a href="#cite_note-FOOTNOTEGentWalsh1996-10">[10]</a> then using methods from statistical physics by Mertens,<a href="#cite_note-FOOTNOTEMertens1998-11">[11]</a><a href="#cite_note-FOOTNOTEMertens2001130-12">[12]</a> and later proved by <a href="Christian_Borgs" title="Christian Borgs">Borgs</a>, <a href="Jennifer_Tour_Chayes" title="Jennifer Tour Chayes">Chayes</a>, and Pittel.<a href="#cite_note-FOOTNOTEBorgsChayesPittel2001-13">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Probabilistic_version">Probabilistic version</h2></div>

A related problem, somewhat similar to the <a href="Birthday_paradox" class="mw-redirect" title="Birthday paradox">Birthday paradox</a>, is that of determining the size of the input set so that we have a probability of one half that there is a solution, under the assumption that each element in the set is randomly selected with uniform distribution between 1 and some given value. The solution to this problem can be counter-intuitive, like the birthday paradox.

<div class="mw-heading mw-heading2"><h2 id="Variants_and_generalizations">Variants and generalizations</h2></div>

Equal-cardinality partition is a variant in which both parts should have an equal number of items, in addition to having an equal sum. This variant is NP-hard too.<a href="#cite_note-Garey_&_Johnson-5">[5]</a>: SP12 Proof. Given a standard Partition instance with some n numbers, construct an Equal-Cardinality-Partition instance by adding n zeros. Clearly, the new instance has an equal-cardinality equal-sum partition iff the original instance has an equal-sum partition. See also <a href="Balanced_number_partitioning" title="Balanced number partitioning">Balanced number partitioning</a>.

Product partition is the problem of partitioning a set of integers into two sets with the same product (rather than the same sum). This problem is <a href="Strong_NP-completeness" title="Strong NP-completeness">strongly NP-hard</a>.<a href="#cite_note-14">[14]</a>

Kovalyov and Pesch<a href="#cite_note-15">[15]</a> discuss a generic approach to proving NP-hardness of partition-type problems.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

One application of the partition problem is for manipulation of <a href="Elections" class="mw-redirect" title="Elections">elections</a>. Suppose there are three candidates (A, B and C). A single candidate should be elected using a voting rule based on scoring, e.g. the veto rule (each voter vetoes a single candidate and the candidate with the fewest vetoes wins). If a coalition wants to ensure that C is elected, they should partition their votes among A and B so as to maximize the smallest number of vetoes each of them gets. If the votes are weighted, then the problem can be reduced to the partition problem, and thus it can be solved efficiently using CKK. The same is true for any other voting rule that is based on scoring.<a href="#cite_note-Walsh_324–329-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-FOOTNOTEKorf1998-1">^ <a href="#cite_ref-FOOTNOTEKorf1998_1-0">a</a> <a href="#cite_ref-FOOTNOTEKorf1998_1-1">b</a> <a href="#CITEREFKorf1998">Korf 1998</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHayes2002" class="citation cs2"><a href="Brian_Hayes_(scientist)" title="Brian Hayes (scientist)">Hayes, Brian</a> (March–April 2002), <a rel="nofollow" class="external text" href="http://bit-player.org/bph-publications/AmSci-2002-03-Hayes-NPP.pdf">"The Easiest Hard Problem"</a> (PDF), <a href="American_Scientist" title="American Scientist">American Scientist</a>, vol. 90, no. 2, Sigma Xi, The Scientific Research Society, pp. 113–117, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/27857621">27857621</a></cite>

</li>

<li id="cite_note-FOOTNOTEMertens2006[httpsbooksgooglecombooksid4YD6AxV95zECpgPA125_125]-3"><a href="#cite_ref-FOOTNOTEMertens2006[httpsbooksgooglecombooksid4YD6AxV95zECpgPA125_125]_3-0">^</a> <a href="#CITEREFMertens2006">Mertens 2006</a>, p. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125">125</a>.

</li>

<li id="cite_note-multi-4"><a href="#cite_ref-multi_4-0">^</a> <cite id="CITEREFKorf2009" class="citation conference cs1"><a href="Richard_E._Korf" title="Richard E. Korf">Korf, Richard E.</a> (2009). <a rel="nofollow" class="external text" href="http://ijcai.org/papers09/Papers/IJCAI09-096.pdf">Multi-Way Number Partitioning</a> (PDF). <a href="IJCAI" class="mw-redirect" title="IJCAI">IJCAI</a>.</cite>

</li>

<li id="cite_note-Garey_&_Johnson-5">^ <a href="#cite_ref-Garey_&_Johnson_5-0">a</a> <a href="#cite_ref-Garey_&_Johnson_5-1">b</a> <cite id="CITEREFGareyJohnson1979" class="citation book cs1">Garey, Michael; Johnson, David (1979). <a rel="nofollow" class="external text" href="https://archive.org/details/computersintract0000gare">Computers and Intractability; A Guide to the Theory of NP-Completeness</a>. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/computersintract0000gare/page/96">96–105</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7167-1045-5</bdi>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFGoodrich" class="citation web cs1">Goodrich, Michael. <a rel="nofollow" class="external text" href="https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf">"More NP complete and NP hard problems"</a> (PDF).</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFHans_KellererUlrich_PferschyDavid_Pisinger2004" class="citation book cs1">Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=u5DB7gck08YC&pg=PA97">Knapsack problems</a>. Springer. p. 97. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540402862</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFMartelloToth1990" class="citation book cs1">Martello, Silvano; Toth, Paolo (1990). <a rel="nofollow" class="external text" href="https://archive.org/details/knapsackproblems0000mart/page/105">"4 Subset-sum problem"</a>. Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/knapsackproblems0000mart/page/105">105–136</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-92420-3</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1086874">1086874</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFKorf1995" class="citation conference cs1"><a href="Richard_E._Korf" title="Richard E. Korf">Korf, Richard E.</a> (1995-08-20). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/1625855.1625890">"From approximate to optimal solutions: a case study of number partitioning"</a>. Proceedings of the 14th International Joint Conference on Artificial Intelligence. IJCAI'95. Vol. 1. Montreal, Quebec, Canada: Morgan Kaufmann Publishers. pp. 266–272. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-363-9</bdi>.</cite>

</li>

<li id="cite_note-FOOTNOTEGentWalsh1996-10"><a href="#cite_ref-FOOTNOTEGentWalsh1996_10-0">^</a> <a href="#CITEREFGentWalsh1996">Gent & Walsh 1996</a>.

</li>

<li id="cite_note-FOOTNOTEMertens1998-11"><a href="#cite_ref-FOOTNOTEMertens1998_11-0">^</a> <a href="#CITEREFMertens1998">Mertens 1998</a>.

</li>

<li id="cite_note-FOOTNOTEMertens2001130-12"><a href="#cite_ref-FOOTNOTEMertens2001130_12-0">^</a> <a href="#CITEREFMertens2001">Mertens 2001</a>, p. 130.

</li>

<li id="cite_note-FOOTNOTEBorgsChayesPittel2001-13"><a href="#cite_ref-FOOTNOTEBorgsChayesPittel2001_13-0">^</a> <a href="#CITEREFBorgsChayesPittel2001">Borgs, Chayes & Pittel 2001</a>.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFNgBarketauChengKovalyov2010" class="citation journal cs1">Ng, C. T.; Barketau, M. S.; Cheng, T. C. E.; Kovalyov, Mikhail Y. (2010-12-01). <a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0377221710003905">""Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation"</a>. European Journal of Operational Research. 207 (2): 601–604. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejor.2010.05.034">10.1016/j.ejor.2010.05.034</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0377-2217">0377-2217</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFKovalyovPesch2010" class="citation journal cs1">Kovalyov, Mikhail Y.; Pesch, Erwin (2010-10-28). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2010.08.001">"A generic approach to proving NP-hardness of partition type problems"</a>. Discrete Applied Mathematics. 158 (17): 1908–1912. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2010.08.001">10.1016/j.dam.2010.08.001</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0166-218X">0166-218X</a>.</cite>

</li>

<li id="cite_note-Walsh_324–329-16"><a href="#cite_ref-Walsh_324–329_16-0">^</a> <cite id="CITEREFWalsh2009" class="citation conference cs1 cs1-prop-location-test"><a href="Toby_Walsh" title="Toby Walsh">Walsh, Toby</a> (2009-07-11). <a rel="nofollow" class="external text" href="https://www.ijcai.org/Proceedings/09/Papers/062.pdf">"Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule"</a> (PDF). Written at Pasadena, California, USA. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco, California, USA: <a href="Morgan_Kaufmann_Publishers_Inc." class="mw-redirect" title="Morgan Kaufmann Publishers Inc.">Morgan Kaufmann Publishers Inc.</a> pp. 324–329. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200710070551/https://www.ijcai.org/Proceedings/09/Papers/062.pdf">Archived</a> (PDF) from the original on 2020-07-10. Retrieved 2021-10-05.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBorgsChayesPittel2001" class="citation cs2">Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), "Phase transition and finite-size scaling for the integer partitioning problem", Random Structures and Algorithms, 19 (3–4): 247–288, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9577">10.1.1.89.9577</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Frsa.10004">10.1002/rsa.10004</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6819493">6819493</a></cite></li>

<li><cite id="CITEREFGentWalsh1996" class="citation conference cs1">Gent, Ian; Walsh, Toby (August 1996). "Phase Transitions and Annealed Theories: Number Partitioning as a Case Study". In Wolfgang Wahlster (ed.). Proceedings of 12th European Conference on Artificial Intelligence. ECAI-96. John Wiley and Sons. pp. 170–174. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.4475">10.1.1.2.4475</a>.</cite></li>

<li><cite id="CITEREFGentWalsh1998" class="citation cs2">Gent, Ian; Walsh, Toby (1998), "Analysis of Heuristics for Number Partitioning", Computational Intelligence, 14 (3): 430–451, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.4980">10.1.1.149.4980</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2F0824-7935.00069">10.1111/0824-7935.00069</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15344203">15344203</a></cite></li>

<li><cite id="CITEREFKorf1998" class="citation cs2"><a href="Richard_E._Korf" title="Richard E. Korf">Korf, Richard E.</a> (1998), "A complete anytime algorithm for number partitioning", Artificial Intelligence, 106 (2): 181–203, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.993">10.1.1.90.993</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0004-3702%2898%2900086-1">10.1016/S0004-3702(98)00086-1</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-3702">0004-3702</a></cite></li>

<li><cite id="CITEREFMertens1998" class="citation cs2">Mertens, Stephan (November 1998), "Phase Transition in the Number Partitioning Problem", Physical Review Letters, 81 (20): 4281–4284, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cond-mat/9807077">cond-mat/9807077</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1998PhRvL..81.4281M">1998PhRvL..81.4281M</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.81.4281">10.1103/PhysRevLett.81.4281</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119541289">119541289</a></cite></li>

<li><cite id="CITEREFMertens2001" class="citation cs2">Mertens, Stephan (2001), "A physicist's approach to number partitioning", Theoretical Computer Science, 265 (1–2): 79–108, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cond-mat/0009230">cond-mat/0009230</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2801%2900153-0">10.1016/S0304-3975(01)00153-0</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16534837">16534837</a></cite></li>

<li><cite id="CITEREFMertens2006" class="citation book cs1">Mertens, Stephan (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=4YD6AxV95zEC&pg=PA125">"The Easiest Hard Problem: Number Partitioning"</a>. In Allon Percus; Gabriel Istrate; <a href="Cris_Moore" class="mw-redirect" title="Cris Moore">Cristopher Moore</a> (eds.). Computational complexity and statistical physics. USA: Oxford University Press. pp. 125–140. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cond-mat/0310317">cond-mat/0310317</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2003cond.mat.10317M">2003cond.mat.10317M</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780195177374</bdi>.</cite></li>

<li><cite id="CITEREFMertens1999" class="citation arxiv cs2">Mertens, Stephan (1999), "A complete anytime algorithm for balanced number partitioning", <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/9903011">cs/9903011</a></cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-24" href="https://en.wikipedia.org/wiki/?title=Partition_problem&oldid=1297073699">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>